import java.util.List;

/*
题目描述：合并两个排序的链表
方法：使用递归，注意对空指针的特殊处理
 */
public class E25 {
    public static void main(String[] args) {
        ListNode head1 = new ListNode(1);
        head1.next = new ListNode(3);
        head1.next.next = new ListNode(5);
        head1.next.next.next = new ListNode(7);
        head1.next.next.next.next = new ListNode(9);
        head1.next.next.next.next.next = new ListNode(10);

        ListNode head2 = new ListNode(2);
        head2.next = new ListNode(4);
        head2.next.next = new ListNode(6);
        head2.next.next.next = new ListNode(8);
        head2.next.next.next.next = new ListNode(10);

        ListNode res = Merge(head1, head2);

        while(res != null){
            System.out.print(res.value + "->");
            res = res.next;
        }
        System.out.println("null");
    }

    public static ListNode Merge(ListNode list1,ListNode list2) {
        if(list1 == null){
            return list2;
        }
        else if(list2 == null){
            return list1;
        }

        ListNode mergedHead = null;
        if(list1.value < list2.value){
            mergedHead = list1;
            mergedHead.next = Merge(list1.next, list2);
        }
        else{
            mergedHead = list2;
            mergedHead.next = Merge(list1, list2.next);
        }
        return mergedHead;
    }
}
